#include "LinkTree.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//树节点
struct TreeNode
{
    TreeElementType data;
    struct TreeNode *parent;//双亲节点
    DLlist childs;//孩子节点列表
};

TNode *CreateTreeNode(TreeElementType element)
{
    TNode * newNode = (TNode*)malloc(sizeof(TNode));
    if(newNode == NULL)
    {
        return NULL;
    }
    
    newNode->data = element;
    newNode->parent = NULL;
    InitDLlist(&newNode->childs);
    return newNode;
}

void FreeTreeNode(void *n)
{
    TNode *freeNode = (TNode *)n;
    if(freeNode == NULL)
        return;
    
    ClearDLlist(&freeNode->childs,FreeTreeNode);
    free(freeNode);
}

void ClearLinkTree(void *tree)
{
    if(tree == NULL)
        return;
    LTree *tp = (LTree*)tree;
    FreeTreeNode(tp->root);
    free(tp);
}

void* GetTreeNodeData(TNode *node)
{
    return node->data;
}

void ConnectBranch(TNode *parent, TNode *child)
{
    if(parent == NULL || child == NULL)
        return;

    child->parent = parent;
    InsertDLlistTail(&parent->childs, child);
}

bool IsNodeEqual(void *ptr1, void *ptr2)
{
    //链表里的节点
    TNode *node1 = (TNode*)ptr1;
    //要删除的节点
    TNode *node2 = (TNode*)ptr2;
    return node1 == node2;
}

void DisconnectBranch(TNode *parent, TNode *child)
{
    if(parent == NULL || child == NULL)
    return;
    if(child->parent != parent)
    {
        printf("两个节点不是父子关系！\n");
        return;
    }
    child->parent = NULL;
    RemoveByElement(&parent->childs,child,IsNodeEqual,NULL);
}

void TravelTreeNode(TNode *node,int deepth, void (*funcPtr)(void*))
{
    if(node == NULL || funcPtr == NULL)
        return;

    if(node->parent != NULL)
    {
        for(int i = 0; i < deepth-1; i++)
            printf("    ");
            if(deepth >= 1)
            printf("|____");
        funcPtr(node->data);
    }
        
    //打印所有的孩子
    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        TravelTreeNode((TNode*)travelPoint->next->data,deepth+1,funcPtr);
        travelPoint = travelPoint->next;
    }
}

TNode *FindChildNode(TNode *parent, void *value, bool (*funcPtr)(void *, void *))
{
    DLNode *travelPoint = parent->childs.head;
    while(travelPoint->next != NULL)
    {
        TNode *child = (TNode*)travelPoint->next->data;
        if(funcPtr(child->data,value) == true)
            return child;
        travelPoint = travelPoint->next;
    }
    return NULL;
}

struct LinkTree
{
    TNode *root;
};

LTree *InitLinkTree()
{
    LTree *tree = (LTree*)malloc(sizeof(LTree));
    if(tree == NULL)
    {
        printf("initTree error!\n");
        return NULL;
    }

    tree->root = CreateTreeNode(NULL);
    return tree;
}

TNode *GetTreeRoot(LTree *tree)
{
    return tree->root;
}

TNode *FindTreeNode(TNode *node, void *value, bool (*funcPtr)(void *, void *))
{
    if(node == NULL || funcPtr == NULL)
        return NULL;
    //符合条件
    if(node->parent != NULL  && funcPtr(node->data,value) == true)
    {
        return node;
    }

    TNode *targetNode = NULL;
    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        targetNode = FindTreeNode((TNode*)travelPoint->next->data,value,funcPtr);
        if(targetNode != NULL)
            return targetNode;
        travelPoint = travelPoint->next;
    }
    return targetNode;
}

TNode *FindLinkTreeNode(LTree *tree, void *value, bool (*funcPtr)(void *, void *))
{

    return FindTreeNode(GetTreeRoot(tree),value,funcPtr);
}

void FindAllLF(TNode *node, DLlist *list)
{
    if(node == NULL)
        return;

    //node本身是叶子
    if(node->childs.len == 0)
    {
        InsertDLlistTail(list,node);
        return;
    }
    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        FindAllLF((TNode*)travelPoint->next->data,list);
        travelPoint = travelPoint->next;
    }
    
}
DLlist FindAllLeafBranches(LTree *tree)
{
    DLlist list;
    InitDLlist(&list);
    FindAllLF(tree->root,&list);
    return list;
}



void TravelTree(LTree *tree, void (*funcPtr)(void*))
{
    TravelTreeNode(GetTreeRoot(tree),-1,funcPtr);
}

int GetNodeHeight(TNode *node)
{
    if(node == NULL)
        return 0;

    int height = 0;
    DLNode *travelPoint = node->childs.head;
    while(travelPoint->next != NULL)
    {
        int childHeight = GetNodeHeight((TNode*)travelPoint->next->data);
        
        height = height > childHeight ? height : childHeight;
        travelPoint = travelPoint->next;
    }
    return height+1;
}

int GetTreeHeight(LTree *tree)
{
    return GetNodeHeight(tree->root);
}
